The present invention relates to an error-checking scheme for digital data processing systems and more particularly to such a scheme employing a pair of parity bits which enable the detection of most common errors occurring in either data or address.
Digital data processing systems, as that term is presently understood, involve the rapid and repetitive transmission of data in binary form as well as the periodic storage and recall of such data. In both the transmission and storing of data, the destination of the binary data is typically designated by an address which is also coded in binary form. In the calling forth of such data either from storage or from an originating source operative on demand, the source is designated by an address, again coded in binary form. Thus, at any given time, there is typically associated with any basic quantity of binary data a corresponding binary address. This is particularly true in modern so-called mini-computer systems in which most data communication takes place over a common bus interconnecting all of the sub-components of the computer system. In such systems, peripheral devices, such as disk and tape memories and, graphic systems, modems and other input/output devices, are assigned addresses which are, for most internal purposes, comparable to the designations given to locations or addresses in the usual random access central memory for the computer.
In handling binary data, the most standard or common grouping of data is the "byte" usually considered to be 8 individual binary bits. Correspondingly, memories for use with digital data processing systems are typically organized so that each address stores either a byte or a multiple number of bytes. In order to check whether data has been properly stored and/or recalled from a computer memory, it has been relatively common practice to generate and store with each byte an additional or ninth bit designated a parity bit. The value of the parity bit is typically set so that the total number of positive or true bits will be either always even or always odd, depending upon the particular design employed. As is understood, such a bit can be generated from the data byte by a tree structure of exclusive OR gates. Such parity bits have also typically been utilized to check the accuracy of transmission of binary data over communication links of various types. In the case of either the memory or the transmission link, the receiving component then can independently generate a parity value from the data received and compare that with the parity bit sourced with the data.
Except in automatic error correction systems, typically requiring relatively elaborate, special-purpose circuitry, most parity systems proposed heretofore have employed multiple parity bits only when multiple byte data words are being processed, each parity bit being associated with the respective data byte only. Similarly, when messages including addresses have been communicated, it has been proposed to provide parity bits for all data being communicated, including binary addresses, but again with each parity bit being associated with a corresponding byte of the binary data including those bytes constituting the address.
While the parity systems described above have been useful and widely adopted, it has been accepted that there are various types of failures and losses of data which such systems will not detect. In memory systems, for example, there are four types of errors which are not uncommon. Herein, the phrase "not common" must be understood as a relative term since the success of digital data processing systems generally is predicated on the very high degree of reliability obtainable in processing digital signals, as compared with analog signals.
The first type of failure is that a single bit in the stored byte will be improperly stored or recalled. As is understood, the chance of two bits within a byte being wrong is almost astronomical since the probability is based on the square of the probability of a single bit failure. A second type of failure which can expectably occur is that the byte will be returned as all "zeros" due to a particular class of malfunction affecting that memory location. Correspondingly, a third type of failure is that the byte will be read out as all "ones" due to a similar class of failure. A fourth type of failure which can occur is that the memory will read out of the wrong address, either due to a failure of communicating the address to the memory or due to an internal failure within the memory itself. As is understood by those skilled in the art, it is mathematically provable that no one bit parity check can detect all of these types of failure in a binary word with an even number of bits, e.g. a byte. Corresponding failures can occur in communications systems and, again, the same difficulty in reliably detecting all such failures with a single bit parity check exists.